1. Field of the Invention
The present invention relates to an apparatus for connecting nodes, especially, relates to a apparatus and method for interconnecting 3-link nodes, and parallel processing apparatus using the same.
2. Prior Art of the Invention
The parallel processing system can have good performance by managing operation in parallel, simultaneously using multiprocessor. The interconnection network connecting nodes organized multiprocessor and transferring data, is very important component dominating the characteristic and performance of a parallel processing system. Each node in the parallel processing system has multi-link for connecting the adjacent nodes. The number of link connected in nodes and the connecting method of link makes difference of the data transfer method. So, It dominates the characteristic and performance of a parallel processing system.
Currently, the interconnection networks adopted in commercial parallel processing system are mainly the bus, ring, crossbar, mesh, and Hypercube interconnection network. However the bus, ring, crossbar interconnection network have handicap in performance or cost for constructing a large scale parallel processing system, so these are used for constructing a small scale system. The mesh interconnection network can offer 2-dimensional mesh or 2-dimensional torus mesh connection network, when there are four connecting links in node, and can offer 3-dimensional mesh or 3-dimensional torus mesh connection network, when there are six connecting links in node. For example, the ASCI TFLOPS system which has been applied by the Intel organizes two x-y plane mesh interconnection network using five connecting links in node. It is difficult to be organized mesh interconnection network, when the number of connecting links is three. For solving this problem, Ivan Stojmenovic proposed a xe2x80x98Honeycomb interconnection networkxe2x80x99 that is the modification of the mesh connection network, using fixed three connecting links in node in the paper, Ivan Stojmenovic, xe2x80x9cHoneycomb Network: Topological Properties Also Communication Algorithms,xe2x80x9d IEEE Transactions on Parallel Also Distributed Systems, pp 1036-1042, October 1997. The Honeycomb interconnection network has the advantage of the mesh interconnection network that can expand feely using only fixed three links. However, it is difficult to divide Honeycomb interconnection network into 2n (n greater than 1) nodes. So, it is difficult to apply to the normal package method. The Hypercube interconnection network can offer 3-dimension Hypercube interconnection network, when there are three connecting links in node, can offer 4-dimension Hypercube interconnection network, when there are four connecting links in node, and can offer 5-dimension Hypercube interconnection network, when there are five connecting links in node. The Hypercube interconnecting network tends to increase in the number of links connected in node proportionally, as the nodes for connecting increase. For correcting the handicap of the Hypercube interconnection network, the F. P. Preparata et. al. proposed the Cube connected cycle interconnection network in the paper, F. P. Preparata et. al., xe2x80x9cThe cube-connected cycles: A versatile network for parallel computation,xe2x80x9d Communication on ACM, pp 300-309, May 1981. Also, I. Y. Lee et. al. demonstrated the relationship of the Hypercube interconnection network, the Cube connected cycle interconnection network, and the similar interconnection network in the paper, I. Y. Lee et. al., xe2x80x9cRing-Connected Networks and Their Relationship to Cubical Ring Connected Cycles and Dynamic Redundancy Networks,xe2x80x9d IEEE Transactions on Parallel and Distributed Systems, pp 988-996, September 1995. The Cube connected cycle interconnection network is able to connect nŝ2n nodes using links, number of n in node, so it makes a pretty improvement comparing with the Hypercube interconnection network that can connect 2n in node. However there is a limitation to the Cube connected cycle interconnection network, using fixed links in node, namely it is able to connect the maximum twenty four nodes when the number of connecting links is three in node. The R. Shu and others made an improvement in the Hypercube interconnection network and the Cube connected cycle interconnection network, and proposed the Improved Hypercube interconnection network in the paper, R. Shu. al., xe2x80x9cImproved Hypercube Topology for Multiprocessors Computer Systems,xe2x80x9d U.S. Pat. No. 5,170,482, Dec. 8, 1992. The Improved Hypercube interconnection network is able to connect more links, and to shorten data transfer delay time than the existing others. However the Improved Hypercube interconnection network is a organization added connecting links to normal hypercube interconnection network, so by misfortune, it has the problem that it is not able to connect nodes having three connecting links.
FIGS. 1A-1C illustrate methods for connecting nodes using fixed three connecting links in existing parallel processing system. FIG. 1A illustrates the 3-dimensional Hypercube interconnection network. Each node in the 3-dimensional Hypercube interconnection network has three connecting links, and is able to connect the maximum 8 nodes. However when anyone wants to expand nodes, it is impossible to expand nodes because connecting links in each node are added proportionally. FIG. 1B illustrates the Cube connected cycle interconnection network. The Cube connected cycle interconnection network is improved on the Hypercube interconnection network. Namely, it expands more nodes using fixed number of connecting links than the Hypercube interconnection network does. Also it is able to expand dimension of the Hypercube form, using fixed three connecting links. However the connecting structure is complex as dimension increases, and the Cube connected cycle interconnection network is not suitable to normal packaging method installing nodes, 2n nodes in one cabinet. FIG. 1C illustrates the Honeycomb interconnection network. The Honeycomb interconnection network is improved on the Mesh interconnection network that is in a difficult organizing using three connecting links. Namely, it expands more nodes using fixed three connecting links and the connecting structure is simple, expands nodes freely as the Mesh interconnection network does. But it is hard to divide into 2n (n greater than 1) nodes, so the Honeycomb interconnection network is not suitable to normal packaging method installing 2n (n greater than 1) nodes in one cabinet.
An embodiment of the present invention provides a method and apparatus for expanding nodes freely using fixed three connecting links, and for offering a normal packaging method with dividing 2n (n greater than 1) nodes. A three links node interconnection apparatus in parallel processing system, comprises four nodes. The first node has three links connected to other nodes respectively. The second node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of X+ direction, Xxe2x88x92 direction. The third node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of Y+ direction, Yxe2x88x92 direction. Also the fourth node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of Z+ direction, Zxe2x88x92 direction.
A three links node interconnection method in parallel processing system, comprises four steps. The first step is connecting the three links of the first node to other nodes respectively. The second step is connecting one of the links of the second node to the first node, and is making the other two links be in charge of connection of X+ direction, Xxe2x88x92 direction. The third step is connecting one of the links of the third node to the first node, and is making the other two links be in charge of connection of Y+ direction, Yxe2x88x92 direction. Also the fourth step is connecting one of the links of the fourth first node, and is making the other two links be in charge of connection of Z+ direction Zxe2x88x92 direction.
A parallel processing apparatus comprises multiple three links nodes organized four nodes into one group, so it is easy to be divided.
Also, a computer-readable record medium recording instructions is offered for interconnecting the three links nodes to realize the following functions. The first function is connecting the three links of the first node to other nodes respectively. The second function is connecting one of the links of the second node to the first node, and is making the other two links be in charge of connection of X+ direction, Xxe2x88x92 direction. The third function is connecting one of the links of the third node to the first node, and is making the other two links be in charge of connection of Y+ direction, Yxe2x88x92 direction. Also the fourth function is connecting one of the links of the fourth first node, and is making the other two links be in charge of connection of Z+ direction Zxe2x88x92 direction.